/**
 * 892. 三维形体的表面积
 * https://leetcode-cn.com/problems/surface-area-of-3d-shapes/
 */
public class Solutions_892 {
    public static void main(String[] args) {
//        int[][] grid = {{2}};  // output: 10
//        int[][] grid = {{1, 2}, {3, 4}};  // output: 34
//        int[][] grid = {{1, 0}, {0, 2}};  // output: 16
//        int[][] grid = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};  // output: 32
        int[][] grid = {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}};  // output: 46

        int result = surfaceArea(grid);
        System.out.println(result);
    }

    // 分步累加

    /**
     * 例如：int[][] grid = {{1, 2}}，表面积为 14 = 6 + (10 - (1 * 2))
     * 计算 grid[0][0] = 1 时，判断前面与左侧没有相邻立方体，直接加表面积 6
     * 计算 grid[0][1] = 2 时，判断左侧有相邻立方体 1 个，可是在判断之前已经
     * 计算得到当前位置上的表面积为 10，并且加到了 res 中。
     * 那么不做减法操作的话，表面积就会多出来。grid[0][0] 的表面积应该减 1
     * grid[0][1] 的表面积应该也减 1，因为这两个面是相邻的，表面看不到（因此不计算到表面积中）
     * 所以对当前遍历的位置，若前面或左侧有相邻的立方体，那么需要减去的表面积数为
     * Math.min(grid[i][j], grid[i - 1][j]) * 2，乘 2 是因为当前位置与相邻位置的表面积都要相应的减少
     * 比较得到最小值是因为：较矮的立方体会被较高的立方体遮蔽，而被遮蔽的面，即是两个立方体相邻的面 * 2
     */
    public static int surfaceArea(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // [i, j] 位置上有柱子摆放时，计算表面积
                if (grid[i][j] > 0) {
                    // 不管位置上有多少个立方体，上、下的表面积都是 2
                    res += 2;
                    // 前后左右的表面积，每个立方体都可以提供 4 个
                    res += grid[i][j] * 4;

                    /**
                     * 考虑有相邻立方体的情况，表面积就需要相减
                     * res 需要减去的表面积：前面的相邻立方体已经计算到 res 中的表面积
                     *  + 上面计算当前位置上立方体的表面积的和
                     * 最终仅计算得到两个相邻位置上组合立方体后得到的总共表面积
                     */
                    if (i > 0 && grid[i - 1][j] > 0) {
                        // 前面若有相邻立方体
                        res -= Math.min(grid[i][j], grid[i - 1][j]) * 2;
                    }
                    if (j > 0 && grid[i][j - 1] > 0) {
                        // 左侧若有相邻立方体
                        res -= Math.min(grid[i][j], grid[i][j - 1]) * 2;
                    }
                }
            }
        }
        return res;
    }
}
